/*
 * @lc app=leetcode.cn id=395 lang=typescript
 *
 * [395] 至少有 K 个重复字符的最长子串
 */

// @lc code=start
function longestSubstring(s: string, k: number): number {
  const m = s.length;
  // 记录每个字符出现的次数
  const hash: Map<string, number> = new Map();
  for (const char of s) {
    hash.set(char, (hash.get(char) || 0) + 1);
  }
  // 记录分割点
  const delimit: number[] = [];
  for (let i = 0; i < m; i++) {
    if (hash.get(s[i]) < k) delimit.push(i);
  }
  // 最后加入哨兵点，方便计算
  delimit.push(m);
  // 如果分割点只有最后一个，表示当前字符串符合题意
  if (delimit.length === 1) return m;

  // 递归求解子串
  let pre = 0;
  let ans = 0;
  for (const idx of delimit) {
    // 字串长度
    let len = idx - pre;
    // 取最大长度
    ans = Math.max(ans, longestSubstring(s.substr(pre, len), k));
    pre = idx + 1;
  }
  return ans;
}
// @lc code=end
